package com.lwl.Algorithmic_data_structure.归并排序.mycode;

/**
 * 记录数组中每个位置前面（左边）比他小的数的和
 * [6,3,2,1,6,7]
 *
 * answer : [0,0,0,0,6,18] --> 6 + 18 = 24
 */
public class SmallSum {

    public static int smallSum(int[] array)
    {
        if (array == null || array.length < 2){
            return 0;
        }

        return process(array, 0, array.length - 1);
    }

    private static int process(int[] array, int left, int right)
    {
        if (left >= right)
        {
            return 0;
        }

        int mid = left + ((right - left) >> 1);

        return process(array, left, mid)
                + process(array, mid + 1, right)
                + merge(array, left, mid, right);
    }

    private static int merge(int[] array, int left, int mid, int right)
    {
        int[] help = new int[right - left + 1];
        int index = 0;
        int l = left;
        int r = mid + 1;
        //产生的小和之和
        int res = 0;

        while (l <= mid && r <= right)
        {
            //因为题目的需要，这里如果相等的话是要移动右数组的
            if (array[l] < array[r])
            {
                //将当前左数组产生的小和进行累加
                res += array[l] * (right - r + 1);
                help[index++] = array[l++];
            }
            else
            {
                //右数组移动不会产生小和
                help[index++] = array[r++];
            }
        }

        while (l <= mid)
        {
            help[index++] = array[l++];
        }
        while (r <= right)
        {
            help[index++] = array[r++];
        }

        for (int i = 0; i < help.length; i++) {
            array[left + i] = help[i];
        }

        return res;
    }

}
